#include "BTreeNode.h"

#include <iostream>

using namespace std;

// Constructor
BTLeafNode::BTLeafNode()
{
	*((PageId*)(buffer+LEAF_SIB)) = -1;
	*((int*)(buffer+LEAF_NKEYS)) = 0;
	*((int*)(buffer+LEAF_FLAG)) = IS_LEAF;

#ifdef DEBUG
	cerr << ">> New leaf node created\n";
	cerr << "size: " << this->getKeyCount() << ", ";
	cerr << "next sibling location: " << this->getNextNodePtr() << endl;
#endif
}

// Constructor
BTNonLeafNode::BTNonLeafNode()
{
	*((int*)(buffer+NONLEAF_NKEYS)) = 0;
	*((int*)(buffer+LEAF_FLAG)) = IS_NONLEAF;
	
#ifdef DEBUG_NODES
	cerr << ">> New nonleaf node created\n";
	cerr << "size: " << this->getKeyCount() << endl;
#endif
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, this->buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, this->buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	return *((int*)(buffer+LEAF_NKEYS));
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int i = getKeyCount() - 1;
	RidKey* current;
	RidKey newkey;
	
	newkey.rid.pid = rid.pid;
	newkey.rid.sid = rid.sid;
	newkey.key = key;
	
	// If node is already full, then error
	if (getKeyCount() >= MAX_LEAF_KEYS) {
		fprintf(stderr, "Error from leaf::insert: node full while inserting %d\n", key);
		fprintf(stderr, "keycount = %d, maxleafkeys = %d\n", getKeyCount(), MAX_LEAF_KEYS);
		return RC_NODE_FULL;
	}
	
	// If this is the first insertion
	current = (RidKey*)(buffer+LEAF_KEYS);
	if (getKeyCount() == 0) {
		current->key = newkey.key;
		current->rid.pid = newkey.rid.pid;
		current->rid.sid = newkey.rid.sid;
	}
	// Counting from last
	while (i >= 0) {
	
		current = (RidKey*)(buffer+LEAF_KEYS + (i * sizeof(RidKey)));
		
		if (getKeyCount() == 0) {
			current->key = newkey.key;
			current->rid.pid = newkey.rid.pid;
			current->rid.sid = newkey.rid.sid;
			break;
		}
	
		// If the new key is still smaller than the current key
		if (newkey.key < current->key) {
			// Copy current key to the next slot
			(current+1)->key = current->key;
			(current+1)->rid.pid = current->rid.pid;
			(current+1)->rid.sid = current->rid.sid;
			// If new key is smaller than all keys, insert new key here
			if (i == 0) {
				current->key = newkey.key;
				current->rid.pid = newkey.rid.pid;
				current->rid.sid = newkey.rid.sid;
			}
		// If this is the correct place for the new key, insert here
		} else {
			(current+1)->key = newkey.key;
			(current+1)->rid.pid = newkey.rid.pid;
			(current+1)->rid.sid = newkey.rid.sid;
			//current->key = current->key;
			//current->rid.pid = current->rid.pid;
			//current->rid.sid = current->rid.sid;
			break;
		}
		i--;
	}
	
	// Increment number of keys
	*((int*)(buffer+LEAF_NKEYS)) = *((int*)(buffer+LEAF_NKEYS)) + 1;
	
#ifdef DEBUG_NODES_INSERT
	cerr << ">> Leaf::insert\n";
	cerr << "new size: " << this->getKeyCount() << endl;
	/*cerr << "contents<key,pid,sid>: ";
	for (int i = 0; i < this->getKeyCount(); i++) {
		current = (RidKey*)(buffer+LEAF_KEYS + (i * sizeof(RidKey)));
		cerr << "(" << current->key << ", " << current->rid.pid << ", "
			 << current->rid.sid << "), ";
	}
	cerr << endl;
	cerr << "Leaf flag: " << *((int*)buffer) << endl;*/
	cerr << endl;
#endif
	
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{	
	RidKey* current;
	RC rv = 0;
	
	// First, insert the key
	rv = this->insert(key,rid); if (rv != 0) return rv;
	
	int nkeys = this->getKeyCount();
	
	// If node is already full, then error
	if (getKeyCount() >= MAX_LEAF_KEYS) {
		fprintf(stderr, "Error from Leaf:insertAndSplit: node too full while inserting %d\n", key);
		fprintf(stderr, "keycount = %d, maxleafkeys = %d\n", getKeyCount(), MAX_LEAF_KEYS);
		return RC_NODE_FULL;
	}
	
	// Insert the latter half into sibling
	for (int i = nkeys/2; i < nkeys; i++) {
		current = (RidKey*)(buffer+LEAF_KEYS + (i * sizeof(RidKey)));
		rv = sibling.insert(current->key,current->rid); if(rv!=0)return rv;
	}
	
	// Split size by half
	*((int*)(buffer+LEAF_NKEYS)) = *((int*)(buffer+LEAF_NKEYS)) / 2;
	
	// Set this node's NextNodePtr to the new sibling
	// TODO: NOTICE! NextNodePtr is still not set!! Need to do outside this function
	
	// Set sibling's NextNodePtr to its appropriate one
	rv = sibling.setNextNodePtr(this->getNextNodePtr()); if(rv!=0)return rv;
	
	// Output new sibling's first key
	current = (RidKey*)(buffer+LEAF_KEYS + (nkeys/2 * sizeof(RidKey)));
	siblingKey = current->key;
	
#ifdef DEBUG_NODES_SPLIT
	cerr << ">> Leaf::insertAndSplit\n";
	cerr << "new size: " << this->getKeyCount() << endl;
	/*cerr << "contents<key,pid,sid>: ";
	for (int i = 0; i < this->getKeyCount(); i++) {
		current = (RidKey*)(buffer+LEAF_KEYS + (i * sizeof(RidKey)));
		cerr << "(" << current->key << ", " << current->rid.pid << ", "
			 << current->rid.sid << "), ";
	}
	cerr << endl;
	cerr << "Leaf flag: " << *((int*)buffer) << endl;*/
	cerr << endl;
#endif
	
	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	RidKey* current;
	int nkeys = this->getKeyCount();
	
	// Iterate through keys from first
	for (int i = 0; i < nkeys; i++) {
		current = (RidKey*)(buffer+LEAF_KEYS + (i * sizeof(RidKey)));
		#ifdef DEBUG_SELECT
		if(i==0)cerr << "smallest key in this leaf is "<<current->key<<endl;
		if(i==nkeys-1)cerr << "largest key in this leaf is "<<current->key<<endl;
		#endif
		
		// return entry number if search key is now less than or equal to current key
		if (current->key >= searchKey) {
			eid = i;
			return 0;
		}
	}
	
	return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	RidKey* current;
	int nkeys = this->getKeyCount();
	
	// Check that entry number is smaller than number of entries
	if (eid < nkeys) {
		current = (RidKey*)(buffer+LEAF_KEYS + (eid * sizeof(RidKey)));
		
		// Output the entry's key and RecordId
		key = current->key;
		rid.pid = current->rid.pid;
		rid.sid = current->rid.sid;
	} else {
		fprintf(stderr, "Leaf::readEntry: No such record: eid=%d but nkeys=%d\n", eid,nkeys);
		return RC_NO_SUCH_RECORD;
	}
	
	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	return *((PageId*)(buffer+LEAF_SIB));
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
#ifdef DEBUG_NODES
	cerr << ">> Leaf::setNextNodePtr\n";
	cerr << "old sibling: " << this->getNextNodePtr() << endl;
#endif

	*((PageId*)(buffer+LEAF_SIB)) = pid;

#ifdef DEBUG_NODES
	cerr << "new sibling: " << this->getNextNodePtr() << endl;
#endif
	
	return 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, this->buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, this->buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	return *((int*)(buffer+NONLEAF_NKEYS));
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	int nkeys = this->getKeyCount();
	int curkey; // holds key values
	int curpid; // holds PageId numbers
	int i = nkeys - 1;
	
	if (getKeyCount() >= MAX_NONLEAF_KEYS) {
		fprintf(stderr, "NonLeaf::insert: node too full while inserting %d\n", key);
		fprintf(stderr, "keycount = %d, maxleafkeys = %d\n", getKeyCount(), MAX_LEAF_KEYS);
		return RC_NODE_FULL;
	}
	
	if (nkeys == 0) {
		// Get current key
		curkey = *((int*)(buffer+NONLEAF_KEYS + i * sizeof(int)));
		curpid = *((PageId*)(buffer+NONLEAF_PIDS + (i+1) * sizeof(PageId)));
		
		*((int*)(buffer + NONLEAF_KEYS + (i) * sizeof(int))) = key;
		*((PageId*)(buffer+NONLEAF_PIDS + (i+1) * sizeof(PageId))) = pid;
	}
	while (i >= 0) {
		// Get current key
		curkey = *((int*)(buffer+NONLEAF_KEYS + i * sizeof(int)));
		curpid = *((PageId*)(buffer+NONLEAF_PIDS + (i+1) * sizeof(PageId)));
		
		// If new key is still smaller than current key
		if (key < curkey) {
			// Move over by one
			*((int*)(buffer+NONLEAF_KEYS + (i+1) * sizeof(int))) = curkey;
			*((PageId*)(buffer+NONLEAF_PIDS + (i+2) * sizeof(PageId))) = curpid;
			
			// If new key is smaller than all keys, insert new key here
			*((int*)(buffer+NONLEAF_KEYS + (i) * sizeof(int))) = key;
			*((PageId*)(buffer+NONLEAF_PIDS + (i+1) * sizeof(PageId))) = pid;
			
		// Found the right place
		} else {
			// Insert here
			*((int*)(buffer+NONLEAF_KEYS + (i+1) * sizeof(int))) = key;
			*((PageId*)(buffer+NONLEAF_PIDS + (i+2) * sizeof(PageId))) = pid;
			
			*((int*)(buffer+NONLEAF_KEYS + (i) * sizeof(int))) = curkey;
			*((PageId*)(buffer+NONLEAF_PIDS + (i+1) * sizeof(PageId))) = curpid;
			break;
		}
		i--;
	}
	
	// Update number of keys
	*((int*)(buffer+NONLEAF_NKEYS)) = nkeys + 1;
	
#ifdef DEBUG_NODES_INSERT
	cerr << ">> NonLeaf::insert\n";
	cerr << "new size: " << this->getKeyCount() << endl;
	/*cerr << "contents<key,pid>: ";
	for (int i = 0; i < this->getKeyCount(); i++) {
		curkey = *((int*)(buffer+NONLEAF_KEYS + i * sizeof(int)));
		curpid = *((PageId*)(buffer+NONLEAF_PIDS + (i+1) * sizeof(PageId)));
		if (i == 0) {
			cerr << *((PageId*)(buffer+NONLEAF_PIDS)) << "), ";
		}
		cerr << "(" << curkey << ", " << curpid << "), ";
	}
	cerr << endl;
	cerr << "Leaf flag: " << *((int*)buffer) << endl;*/
	cerr << endl;
#endif
	
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	int curkey;
	PageId curpid;
	PageId pid2;
	RC rv = 0;
	
	if (getKeyCount() >= MAX_NONLEAF_KEYS) {
		fprintf(stderr, "NonLeaf::insertAndSplit: node too full while inserting %d.\n", key);
		fprintf(stderr, "keycount = %d, maxleafkeys = %d\n", getKeyCount(), MAX_LEAF_KEYS);
		return RC_NODE_FULL;
	}
	
	// First, insert the node
	rv = this->insert(key, pid); if(rv!=0)return rv;
	
	int nkeys = this->getKeyCount();
	
	// Initialize the sibling
	curkey = *(int*)(buffer+NONLEAF_KEYS + sizeof(int)*(nkeys/2));
	curpid = *(PageId*)(buffer+NONLEAF_PIDS + sizeof(PageId)*(nkeys/2));
	pid2 = *(PageId*)(buffer+NONLEAF_PIDS + sizeof(PageId)*(nkeys/2+1));
	rv = sibling.initializeRoot(curpid, curkey, pid2); if(rv!=0)return rv;
	midKey = curkey; // output the midkey
	
	// Insert the latter half into sibling
	for (int i = nkeys/2 + 1; i < nkeys; i++) {
		curkey = *(int*)(buffer + NONLEAF_KEYS + sizeof(int)*(i));
		curpid = *(PageId*)(buffer+NONLEAF_PIDS + sizeof(PageId)*(i+1));
		rv = sibling.insert(curkey,curpid); if(rv!=0)return rv;
	}
	
	// Split size by half
	*((int*)(buffer+NONLEAF_NKEYS)) = *((int*)(buffer+NONLEAF_NKEYS)) / 2;
	
	nkeys = this->getKeyCount();
	
#ifdef DEBUG_NODES_SPLIT
	cerr << ">> NonLeaf::insertAndSplit\n";
	cerr << "new size: " << this->getKeyCount() << endl;
	/*cerr << "contents<key,pid>: ";
	for (int i = 0; i < this->getKeyCount(); i++) {
		curkey = *((int*)(buffer + NONLEAF_KEYS + i * sizeof(int)));
		curpid = *((PageId*)(buffer+NONLEAF_PIDS + (i+1) * sizeof(PageId)));
		if (i == 0) {
			cerr << *((PageId*)(buffer+NONLEAF_PIDS)) << "), ";
		}
		cerr << "(" << curkey << ", " << curpid << "), ";
	}
	cerr << endl;
	cerr << "Leaf flag: " << *((int*)buffer) << endl;*/
	cerr << endl;
#endif
	
	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int i = 0;
	int nkeys = this->getKeyCount();
	int curkey = *((int*)(buffer + NONLEAF_KEYS));
	
	// As soon as you find a key larger than the search key, return pid
	while (i < nkeys) {
		curkey = *((int*)(buffer + NONLEAF_KEYS + i*sizeof(int)));
		if (searchKey < curkey) {
			pid = *((PageId*)(buffer+NONLEAF_PIDS + i*sizeof(PageId)));
			#ifdef DEBUG_SELECT
			fprintf(stderr, "searchKey %d smaller than key curkey %d in %dth iteration\n",searchKey,curkey,i);
			#endif
			return 0;
		}
		i++;
	}
	
	// If search key is larger than all keys in node, return last pid
	pid = *((PageId*)(buffer+NONLEAF_PIDS + i*sizeof(PageId)));
	
	#ifdef DEBUG_SELECT
	fprintf(stderr, "searchKey %d was bigger than biggest key %d\n",searchKey,curkey);
	#endif
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	// Initial key
	*((int*)(buffer + NONLEAF_KEYS)) = key;
	// pid for anything less than key
	*((PageId*)(buffer+NONLEAF_PIDS)) = pid1;
	// pid for anything greater than key
	*((PageId*)(buffer+NONLEAF_PIDS + sizeof(PageId))) = pid2;
	// number of keys in node
	*((int*)(buffer+NONLEAF_NKEYS)) = 1;

#ifdef DEBUG_NODES
	int curkey;
	int curpid;
	
	cerr << ">> NonLeaf::initializeRoot\n";
	cerr << "new size: " << this->getKeyCount() << endl;
	/*cerr << "contents<key,pid>: ";
	for (int i = 0; i < this->getKeyCount(); i++) {
		curkey = *((int*)(buffer + NONLEAF_KEYS + i * sizeof(int)));
		curpid = *((PageId*)(buffer+NONLEAF_PIDS + (i+1) * sizeof(PageId)));
		if (i == 0) {
			cerr << *((PageId*)(buffer+NONLEAF_PIDS)) << "), ";
		}
		cerr << "(" << curkey << ", " << curpid << "), ";
	}*/
	cerr << endl;
#endif
	
	return 0;
}

bool BTNonLeafNode::isNotLeaf() {
	int flag = *((int*)(buffer+LEAF_FLAG));
	if (flag == IS_NONLEAF) return true;
	else return false;
}
